package leetcode.code787.CheapestFlightsWithinKStops;

import java.util.HashMap;
import java.util.Map;

/**
 *
 * 算法 决定 数据结构的典型代表
 *
 * @author Max
 * @date 2021年8月24日
 * @description
 */
public class Solution78706 extends CheapestFlightsWithinKStops {

	@Override
	public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
		Map<Integer, Map<Integer, Integer>> map = new HashMap<>();// key = des , map = srcmap
		for (int[] flight : flights) {
			if (map.containsKey(flight[1])) {
				Map<Integer, Integer> temp = map.get(flight[1]);
				temp.put(flight[0], flight[2]);
			} else {
				Map<Integer, Integer> temp = new HashMap<>();
				temp.put(flight[0], flight[2]);
				map.put(flight[1], temp);
			}
		}
		int ans[][] = new int[k + 1][n];
		int min = 1000001;
		for (int to = 0; to < n; to++) {
			ans[0][to] = -1;
			if (map.containsKey(to)) {
				if (map.get(to).containsKey(src)) {
					ans[0][to] = map.get(to).get(src);
				}
			}
		}
		if (ans[0][dst] != -1) {
			min = ans[0][dst];
		}
		//一次一次往目标飞，目标是有效目标，记录
		for (int flytimes = 1; flytimes <= k; flytimes++) {
			for (int to = 0; to < n; to++) {
				ans[flytimes][to] = -1;
				if (map.containsKey(to)) {
					for (Integer from : map.get(to).keySet()) {
						if (ans[flytimes - 1][from] != -1) {
							if (ans[flytimes][to] != -1) {
								ans[flytimes][to] = Math.min(ans[flytimes][to],
										ans[flytimes - 1][from] + map.get(to).get(from));
							} else {
								ans[flytimes][to] = ans[flytimes - 1][from] + map.get(to).get(from);
							}
						}
					}
				}
			}
			if (ans[flytimes][dst] != -1)
				min = Math.min(min, ans[flytimes][dst]);
		}
		return min == 1000001 ? -1 : min;
	}

	public static void main(String[] args) {
		Solution78706 so = new Solution78706();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();
	}

}
